"""
设计二叉树三种遍历的实现
    初始化创建 Node,Tree 类；
    将 1-10 添加到二叉树里面(使用 add 函数)；
    将三种遍历过程，最后打印出来。
    效果:
    input:
        [1,2,3,4,5,6,7,8,9,10]
    output:
        中序遍历: [7,3,8,1,9,4,10,'root',5,2,6]
        先序遍历: ['root',1,3,7,8,4,9,10,2,5,6]
        后序遍历： [7,8,3,9,10,4,1,5,6,2,'root']
"""


class Node:
    def __init__(self, data, dad, son1, son2):
        self.data = data
        self.LeftSon = son1
        self.RightSon = son2
        self.Parent = dad


class Tree:
    def __init__(self):
        self.root = Node(data="root", dad=None, son1=None, son2=None)
        self.elements = [self.root]

    def add(self, data):
        node = Node(data=data, dad=None, son1=None, son2=None)
        self.elements.append(node)
        i = self.elements.index(node)
        if i % 2 == 0:
            node.Parent = self.elements[i // 2 - 1]
            node.Parent.RightSon = node
        else:
            node.Parent = self.elements[i // 2]
            node.Parent.LeftSon = node

    def inorder(self, node, results):
        if node.LeftSon != None:
            self.inorder(node.LeftSon, results)
        results.append(node.data)
        if node.RightSon != None:
            self.inorder(node.RightSon, results)
        return results

    def preorder(self, node, results):
        results.append(node.data)
        if node.LeftSon != None:
            self.preorder(node.LeftSon, results)
        if node.RightSon != None:
            self.preorder(node.RightSon, results)
        return results

    def postorder(self, node, results):
        if node.LeftSon != None:
            self.postorder(node.LeftSon, results)
        if node.RightSon != None:
            self.postorder(node.RightSon, results)
        results.append(node.data)
        return results

    def inorder_traversal(self):
        print(self.inorder(self.root, []))

    def preorder_traversal(self):
        print(self.preorder(self.root, []))

    def postorder_traversal(self):
        print(self.postorder(self.root, []))


tree = Tree()
elements = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for element in elements:
    tree.add(element)
tree.inorder_traversal()
tree.preorder_traversal()
tree.postorder_traversal()
